// https://www.lintcode.com/problem/permutations/

public class Solution {
    /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    public List<List<Integer>> permute(int[] nums) {
        // write your code here
        List<List<Integer>> ret = new ArrayList<>();
        if (nums.length > 0) {
            _permute(nums, 0, ret);
        } else {
            ret.add(new ArrayList<>());
        }
        return ret;
    }
    
    protected void _permute(int[] nums, int start, List<List<Integer>> ret) {
        if (start == nums.length) {
            List<Integer> li = new ArrayList<>();
            for (int i : nums) {
                li.add(i);
            }
            ret.add(li);
        } else {
            for (int i = start; i < nums.length; ++i) {
                swap(nums, start, i);
                _permute(nums, start + 1, ret);
                swap(nums, i, start);
            }
        }
    }
    
    protected void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}